Goto

Collaborating Authors

 sqrt 0


Supplementary Text: Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components

Neural Information Processing Systems

For our local hypergraph clustering experiments, we inserted SPARSECARD as a subroutine into the method HYPERLOCAL, which finds a cluster S in a hypergraph H = (V,E) that is localized around an input set Z V. It does so by minimizing the following ratio cut objective: φ(S) = cutH(S) vol(Z S) βvol( Z S), subject to vol( Z S) 0. (35) Here, Z = V\Z denotes the complement set of Z. For a node set T V, vol(T) denotes volume of T, i.e., the sum of node degrees. The term vol(Z S) in the denominator rewards a high overlap between the output cluster S and the input set Z. The second term βvol( Z S) is a penalty for including too many nodes outside the input set Z. This is tuned by a locality parameter β > 0. For smaller values of β, the algorithm will explore a larger region in the hypergraph in search for good clusters.